/*
快速排序（Quicksort）是一种常用且高效的排序算法，基于分治思想。
它通过选择一个“基准”（pivot），然后将数组划分为比基准小和比基准大的两部分，再分别对这两部分递归地应用快速排序，直到整个数组排序完毕。


在这个代码示例中，快速排序函数 quick_sort 接收数组、低索引和高索引作为参数。首先，partition 函数选择最后一个元素作为基准，并将数组分为小于和大于基准的两部分。通过遍历数组，确保所有小于基准的元素在基准的左侧，大于基准的元素在右侧。

quick_sort 函数递归地对基准两侧进行快速排序，直到整个数组排序完毕。递归终止条件是低索引大于或等于高索引，表示已经分割到最小可能的部分。

快速排序的平均时间复杂度为 
𝑂(𝑛log𝑛)
O(nlogn)，最坏情况下为 
𝑂(𝑛2)O(n2)（如数组已经排序）。尽管如此，它通常具有较高的效率，是许多库和框架中默认的排序算法之一。通过随机选择基准或三数取中（median of three）等策略，可以减小出现最坏情况的概率。

*/

#include <stdio.h>

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // 指向小于基准的区域的最后位置

    // 将数组中的元素与基准进行比较并交换位置
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {  // 小于基准时，交换
            i++;  // 增加小于基准的区域
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将基准放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;  // 返回基准的最终位置
}

// 快速排序函数
void quick_sort(int arr[], int low, int high) {
    if (low < high) {  // 递归终止条件
        int pi = partition(arr, low, high);  // 对数组进行分区

        // 递归排序左边和右边
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

int main() {
    // 示例数组
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int size = sizeof(arr) / sizeof(arr[0]);

    // 执行快速排序
    quick_sort(arr, 0, size - 1);

    // 输出排序结果
    printf("排序后的数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}
